package 跳表;

import java.util.Comparator;

public class SkipList<K, V> {

	private static int MAX_LEVEL = 32;
	private static double P = 0.25;
	
	private int size;	// 节点数量
	private Comparator<K> comparator;	// 比较器
	private Node<K, V> first;	// 虚拟头节点
	private int level;	// 当前实际层数
	
	
	
	public SkipList() {
		this(null);
	}
	public SkipList(Comparator<K> comparator) {
		this.comparator = comparator;
		first = new Node<>(null, null, new Node[MAX_LEVEL]);
	}
	
	public int size() {
		return size;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}
	
	public V put(K key, V value) {
		keyNotNullCheck(key);
		// 找到所有层级的前驱节点, 如果找到相同的节点, 直接覆盖返回
		Node<K, V> node = first;
		Node<K, V>[] prevs = new Node[level];	// 记录当前层的前驱节点
		int cmp = -1;
		for (int i = level - 1; i >= 0; i--) {
			while (node.nexts[i] != null && (cmp = compare(key, node.nexts[i].key)) > 0) {
				node = node.nexts[i];
			}
			if (cmp == 0) {
				V oldValue = node.nexts[i].value;
				node.nexts[i].value = value;
				return oldValue;
			}
			prevs[i] = node;
		}
		
		// 插入新的节点
		int newLevel = randomLevel();
		Node<K, V> newNode = new Node<>(key, value, new Node[newLevel]);
		// 更新前驱后继
		for (int i = 0; i < newLevel; i++) {
			if (i >= level) {
				first.nexts[i] = newNode;
			} else {
				newNode.nexts[i] = prevs[i].nexts[i];
				prevs[i].nexts[i] = newNode;
			}
		}
		size++;
		// 更新层数
		level = Math.max(level, newLevel);
		return null;
	}
	
	public V remove(K key) {
		keyNotNullCheck(key);
		Node<K, V> node = first;
		Node<K, V>[] prevs = new Node[level];	// 记录当前层的前驱节点
		int cmp = -1;
		for (int i = level - 1; i >= 0; i--) {
			while (node.nexts[i] != null && (cmp = compare(key, node.nexts[i].key)) > 0) {
				node = node.nexts[i];
			}
			prevs[i] = node;
		}
		
		if (cmp != 0) return null;	// 不存在此节点
		
		// 更新前驱后继
		Node<K, V> removedNode = node.nexts[0];
		for (int i = 0; i < removedNode.nexts.length; i++) {
			prevs[i].nexts[i] = removedNode.nexts[i];
		}
		// 更新节点数量
		size--;
		
		// 更新层数
		int newLevel = level;
		while (--newLevel >= 0 && first.nexts[newLevel]== null) level = newLevel;
			
		return removedNode.value;
	}
	
	public V get(K key) {
		keyNotNullCheck(key);
		Node<K, V> node = first;
		int cmp = -1;
		for (int i = level - 1; i >= 0; i--) {
			while (node.nexts[i] != null && (cmp = compare(key, node.nexts[i].key)) > 0) {
				node = node.nexts[i];
			}
			// 此时node.next == null || node.next.key > key, 判断是否相等: 相等直接返回, 不相等直接跳到下一层寻找
			if (cmp == 0) return node.nexts[i].value;
		}
		return null;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("一共" + level + "层").append("\n");
		for (int i = level - 1; i >= 0; i--) {
			Node<K, V> node = first;
			while (node.nexts[i] != null) {
				sb.append(node.nexts[i]);
				sb.append(" ");
				node = node.nexts[i];
			}
			sb.append("\n");
		}
		return sb.toString();
	}
	
	/**
	 * 检查key是否为null
	 */
	private void keyNotNullCheck(K key) {
		if (key == null) throw new NullPointerException("Key must not be null");
	}
	
	/**
	 * 比较key
	 */
	private int compare(K k1, K k2) {
		if (comparator != null) return compare(k1, k2);
		return ((Comparable<K>)k1).compareTo(k2);
	}
	
	/**
	 * 生成随机层数
	 */
	private int randomLevel() {
		int level = 1;
		while (Math.random() < P && level < MAX_LEVEL) level++;
		return level;
	}
	
	private static class Node<K, V> {
		K key;
		V value;
		Node<K, V>[] nexts;
		public Node(K key, V value, Node<K, V>[] nexts) {
			this.key = key;
			this.value = value;
			this.nexts = nexts;
		}
		@Override
		public String toString() {
			return key + ":" + value + "_" + nexts.length;
		}
		
		
	}
	
}
